package com.ljy.my_study.leetcode.二叉树的层序遍历II;

import com.ljy.my_study.util.TreeNodeUtil;
import com.ljy.my_study.util.TreeNodeUtil.*;

import java.util.*;

/**
 * @author lijunying
 * @date 2021/11/17 16:46
 */
public class TestMain {

//    给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
//
//    例如：
//    给定二叉树 [3,9,20,null,null,15,7],
//
//            3
//            / \
//            9  20
//            /  \
//            15   7
//    返回其自底向上的层序遍历为：
//
//            [
//            [15,7],
//            [9,20],
//            [3]
//            ]
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        TreeNode root=TreeNodeUtil.deserialize("3,9,20,null,null,15,7");
        System.out.println(new TestMain().levelOrderBottom(root));
    }

//    当前先获取最大高度，然后通过数组从大到小索引保存数据
//    也可以通过先获取最大高度，然后通过dfs来从尾返回来获取保存数据
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null){
            return new ArrayList<>();
        }
        int level=maxLevel(root,0);
        List<Integer>[] array=new List[level];
        int size=1;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int newSize=0;
            List<Integer> list=new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode node=queue.poll();
                list.add(node.val);
                if(node.left!=null){
                    queue.add(node.left);
                    newSize++;
                }
                if(node.right!=null){
                    queue.add(node.right);
                    newSize++;
                }
            }
            array[--level]=list;
            size=newSize;
        }
        return Arrays.asList(array);
    }

    private int maxLevel(TreeNode root,int level){
        if(root==null){
            return level;
        }
        return Math.max(maxLevel(root.left,level+1),maxLevel(root.right,level+1));
    }
}
